Modern telecommunication networks include switching networks for transmitting data from a source device to a destination device. Circuit switching and packet switching are commonly used in high-capacity networks. In circuit-switched networks, network resources are established from the sender to receiver before the start of the transfer of the data. The resources remain dedicated to the circuit during the transfer of the data and all of the data follows the same path. By contrast, in packet-switched networks, the data is broken into packets, each of which can take a different route to the destination where the packets are recompiled into the original message.
In packet switching networks the data to be transmitted is split up and encapsulated into data packets along with a destination address of the data. The packet switching network individually routes each data packet through a network of interconnected packet switches based on the destination address in the data packet. The data packets may be routed through different paths in the packet switching network and generally arrive at the destination device in an arbitrary order. At the destination device, the data is reconstructed from the data packets.
Because the packet switch may receive multiple data packets at the input ports that are destined for the same output port, the packet switch often includes an arbiter that determines an order for routing data packets through the packet switch. The input ports of the packet switch issue grant requests to the arbiter for routing data contained in data packets to the output ports. The arbiter then determines whether the output port identified by each grant request is available to receive data. If an output port identified by a grant request is available to receive data, the arbiter selects a grant request that identifies the output port and issues a grant to the input port that issued the selected grant request. The packet switch then routes data contained in a data packet of each input port that received a grant to the output port identified by the selected grant request issued by the input port.
In determining which input port should be granted access, the arbiter commonly performs a form of round robin arbitration to ensure that all the input ports requesting access to the output ports have equal access time. Round robin arbitration is a method of choosing all elements in a list, set, or group equally in some rational order, usually from the top to the bottom of a list and then starting again at the top of the list. Typical round robin arbitration involves assigning priorities according to a predetermined order among the input ports. As message traffic is received, the priorities change so that the last input granted access to a particular output is then given the lowest priority, and the next input in order of priority now has the highest priority. The remaining input ports will have their priorities similarly changed according to the predetermined order.
Round robin algorithms are commonly used for round robin arbitration to select from one among a number of candidates, while insuring that each candidate is treated fairly. In the implementation of a packet switch, the candidates are the input ports. In a round robin algorithm for N candidates, the candidates are typically arranged in a vector such that candidate 1 populates bit 1, candidate 2 populates bit 2, and so on, to create an N bit bus. If candidate A is the winner in the current round, then candidate A+1 has the highest priority in the next round, if A<N, while candidate 1 has the highest priority in the next round if A=N. As such, the candidate from the previous selection always has the lowest priority and N always has a higher priority than 1, unless the previous selection was N.
A typical implementation of the round robin algorithm involves two steps. First, the candidate vector is shifted or rotated so that its bits are organized with the highest priority candidate in bit position 1 according to the algorithm, with the priority successively decreasing until the lowest priority bit is in position N. Then, the lowest bit index with an active candidate is selected as the winning candidate. There is an inherent delay associated with waiting for the candidate vector to be rotated prior to making the winning selection in a round robin arbitration algorithm. The delay resulting from the round robin arbitration ultimately affects the performance of the switch. Accordingly, it is advantageous to reduce this delay as much as possible.
Additionally, some applications of the round robin algorithm require evaluating the acceptability of candidates prior to performing a round robin selection. Typically, this requires testing some attribute of the candidate, accepting all candidates that possess this attribute, and then submitting the accepted candidates to the round robin process. As such, selection of the accepted candidates must be delayed until the attribute on which the selection is based becomes available. This delay also affects the performance of the switch and should be reduced as much as possible.
In light of the above, a need exists for reducing the time required for an arbiter to select data for routing through a switch. A further need exists for reducing the time required for an arbiter to perform a round robin arbitration to select a winning candidate.